import java.util.LinkedList;

public class partitionlist {
    public LinkedList<Integer> partition(LinkedList<Integer> list, int k) {
        LinkedList<Integer> newlist = new LinkedList<>();
        LinkedList<Integer> temp = newlist;
        LinkedList<Integer> newlist1 = new LinkedList<>();
        LinkedList<Integer> temp1 = newlist1;

        LinkedList<Integer> cur = list;
        for(int x: list){
            if(x < k){
                temp.addFirst(x);
            }else {
                temp1.addFirst(x);
            }
        }
        temp.addAll(temp1);
        return newlist;
    }
    public static void main(String[] args) {
        partitionlist obj = new partitionlist();
        LinkedList<Integer> list = new LinkedList<>();
        list.addFirst(3);
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(5);
        list.addFirst(4);

        int k =3;
        LinkedList<Integer> temp = obj.partition(list, k);
        System.out.println(temp);
    }
}
